package DP.子序列.回文问题;

import org.junit.Test;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
单cur要先定终点大基调：
    先定终点：（0，n）的最大回文子序长度
    再方框ci汉译单cur：
        bb         baba
       汉译+2    汉译取min不加2
        ‘’       bab   aba
*/
public class 回文子序_后序问题_516 {
    @Test
    public void test() {
        System.out.println(longestPalindromeSubseq("bbbab"));
    }

    char[] s;
    public int longestPalindromeSubseq(String t) {
        s = t.toCharArray();
        //[i,j]闭区间的最长回文可间隔子序列长度
        int i=0,j=s.length-1;
        return back(i,j);
    }
    private int back(int i, int j) {
        //[i,j]双闭区间，空串‘’是互相超1
        if(i>j){
            return 0;
        }
        //一个字符 双闭应该是相同 不是+1
        if(i==j){
            return 1;
        }
        //相同跳过  （这个相同con，就是向下拆的限制
        if(i<s.length&&j>=0 && s[i]==s[j]){
            //2=相等的ij
            return 2 + back(i+1,j-1) ;
        }else {
            return Math.max(back(i+1,j),back(i,j-1));
        }
    }
}
